package com.fr.lintcode;

import org.junit.Test;

/**
*作者：furong
*日期：2017年2月24日
*时间：下午3:52:54
*/
public class Q412ii {
    /**
     * 两次dp
     * @param ratings Children's ratings
     * @return the minimum candies you must give
     */
    public int candy(int[] ratings) {
        int length = ratings.length;
        if (length == 1) {
            return 1;
        }
        int[] dp = new int[length];
        dp[0] = 1;
        for (int i = 1; i < length; i++) {
            dp[i] = 1;
            if (ratings[i] > ratings[i - 1]) {
                dp[i] = dp[i - 1] + 1;
            }
        }
        for (int i = length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                dp[i] = Math.max(dp[i], dp[i + 1] + 1);
            }
        }
        int sum = 0;
        for (int i : dp) {
            sum += i;
        }
        return sum;
    }

    @Test
    public void testA() {
        int[] ratings = { 1, 2, 4, 4 };
        System.out.println(candy(ratings));
    }
}
